The present invention relates to an incremental sequence completion system and method designed to compute e.g. music sequences in a variety of different contexts and situations, including: Internet adaptive or interactive radio, digital audio broadcasting (DAB) with intelligent scheduling, music recommendation systems, and other innovative Electronic Music Distribution (EMD) services in general. These sequences are generated xe2x80x9citerativelyxe2x80x9d, step by step. The present invention also concerns a system or server adapted to implement such a method.
Advances in networking and transmission of digital multimedia data have made it possible to provide users with huge catalogues of information, such as music catalogues. These advances thus raise not only the problem of distribution, but also the problem of choosing the desired information among huge catalogues.
Such new developments raise music selection problems which may depend on users"" aims or those of content providers. Although modelling a user""s goal in accessing music is very complex, two basic elements, i.e. desire of repetition and desire of surprise, can be identified.
The desire of repetition means that people want to listen to music they already know, or similar to what they already know. Sequences of repeating notes create expectations of the same notes to occur. On the other hand, the desire for surprise is a key to understanding music at all levels of perception.
Of course, these two desires are contradictory, and the issue in music selection is precisely to find the right compromise: provide users with items they already know, or items they do not know but would probably like.
From the viewpoint of record companies, the goal of music delivery is to achieve a better exploitation of the catalogue. Indeed, record companies have problems with the exploitation of their catalogue using standard distribution schemes. For technical reasons, only a small part of the catalogue is actually xe2x80x9cactivexe2x80x9d, i.e. proposed to users, in the form of easily available products. More importantly, the analysis of music sales shows clearly decreases in the sales of albums, and short-term policies based on selling many copies of a limited number of items (hits) are no longer efficient. Additionally, the sales of general-purpose xe2x80x9csamplersxe2x80x9d (e.g. xe2x80x9cBest of love songsxe2x80x9d) are no longer profitable, because users already have the hits, and do not want to buy CDs in which they like only a fraction of the titles. Instead of proposing a small number of hits to a large audience, a natural solution is to increase diversity by proposing more customised albums to users.
The system according to the present invention allows to compute one step in the music sequence generation process. When implementing the inventive system, the server typically receives repeated calls to provide full-fledged EMD services.
For instance, a user may compute the choice of an initial music title by using a device or system of the invention. He thereby starts the procedure from an empty sequence. The system then computes a next title using a sequence containing the first computed title, etc. The system computes only the xe2x80x9cbest next itemxe2x80x9d, sometimes referred to here as xe2x80x9cbextxe2x80x9d, of a given sequence of items. This allows to compute different kinds of continuations, and to take into account possible changes in the user""s taste, or in the sequence heard.
The system according to the present invention takes into account two main parameters:
1) a context of what is listened to, given by a sequence of items that is supposed to have already been heard by the user; and
2) a user profile, defining the taste of the user.
Typically, the items are music titles, and the sequences of music programs composed of a sequence of titles, e.g. interactive Internet Radio and xe2x80x9con-demandxe2x80x9d music compilations.
The system produces the xe2x80x9cbest next itemxe2x80x9d, i.e. xe2x80x9cbextxe2x80x9d: Here, the term xe2x80x9cbextxe2x80x9d means the item proposed by the server which should satisfy two criteria: 1) conforming to the user""s taste, and 2) being consistent within the given context (defined by the sequence).
The main innovative idea of the present invention resides in combining two elements, i.e. 1) an incremental sequence completion system and 2) a standard-user profiling system. The term completion is well known in the field of computing, and refers to the technique of completing by anticipation a sequence of which the first elements are given as an input.
The method in accordance with the present invention is capable of operating interactively. In other words, the user (recipient of the sequence) can send data to the server during the course of a sequence generation to modify the selections to follow in the sequence. These data can e.g. correspond to parameters that form the user profile. A dialogue can thereby be established between the user and the server of the sequence: the server delivers an item of the sequence and the user may, in response, indicate his or her appreciation of that item, e.g. through user profile parameters. The response is taken into account by the server to modifyxe2x80x94if needs bexe2x80x94the corresponding profile accordingly. In this way, the server can evolve in real time by such interactions with the user to provide an increasingly accurate choice of best next items in the sequence, and thereby effect an optimised completion through a better anticipation of the next item of the sequence likely to satisfy the user.
In the present invention, the term xe2x80x9cdatabasexe2x80x9d is used for designating any collection of data, e.g. covering both pre-stored data and dynamically stored data. There are many situations in which it is necessary or desirable to create a sequence of items (e.g. music titles) from a collection of items for which data are available. It is also important that a created sequence is xe2x80x9ccoherentxe2x80x9d, i.e. there should exist a particular relationship between attributes (or descriptors) of the items which constitute a sequence. Typically, the attributes of the items, components of the sequence, should not be too dissimilar, especially for successive items in the same sequence.
A system for producing xe2x80x9ccoherentxe2x80x9d sequences of items in a particular order is known from patent document EP-A-0 961 209. However, this patent deals specifically with sequences having a length that is initially fixed, i.e. known a priori.
The items are generally stored in a database and described in terms of data pairs, each pair respectively consisting of an attribute and the corresponding value. The problem of creating the desired fixed length sequence is treated as xe2x80x9cConstraint Satisfaction Programming (CSP)xe2x80x9d, also disclosed in the above EP application. The sequence to be obtained is specified by formulating a collection of constraints holding on items in the database. Each constraint describes a particular property of the sequence, and the sequence can be specified by any number of constraints.
The items in the database exhibit a particular generic format with associated taxonomies for at least some of the attribute values. Also, the constraints are specified out of a predetermined library of generic constraint classes which have been specially formulated. The special constraint classes allow the expression of desired properties of the target sequence, notably properties of similarity between groups of items, properties of dissimilarity and properties of cardinality. These constraint classes enable the properties of coherent sequences to be expressed in a particularly simple manner.
It is the combination of the use of a generic format for items in the database and the special constraint classes which makes it possible to use CSP solution techniques to solve the combinatorial problem of building an ordered collection of elements satisfying a number of constraints.
Much work has been carried out in user recommendation systems. Most of this work is based on the idea of managing user xe2x80x9cprofilesxe2x80x9d, using some sort of collaborating filtering approach (for instance, the FireFly technology). Similarity measures between profiles allow to compute the closest profiles of a given individual. Data analysis techniques then allow to extract the most common taste of these xe2x80x9cclosexe2x80x9d profiles, which is then recommended to the user.
The concept of the present invention is to combine this technology with another technology, namely an incremental sequence completion system, which make it possible to create sequences of items (and not simply sets of items as in collaborative filtering). Sequences here mean ordered collections of items, as found typically in the context of music listening (e.g. radio programs, concerts, compilations). A technology to produce sequences of items was previously the subject of patent application EP-A 0 961 209 described above. The previous patent application, however, considered fixed-length sequences, and did not explicitly take into account user profiling. Furthermore, it was not fully adapted to incremental sequence generation.
The proposed invention allows not only to propose the items likely to please the user (standard collaborative filtering), but also the items that fit well in the given sequence. Moreover, the invention described here does not compute actual sequences, but is limited to computing the next item in a given sequence. This allows to use the invention in a variety of contexts, for different EMD applications, taking user""s interaction into account as needed.
To this end, there is provided a method of generating incrementally a sequence of items from a database containing the items. The method is characterised in that the sequence is generated by implementing in combination a sequence completion system and a user profiling system, thereby taking into account both sequence coherence and user profile.
Typically, the item comprises at least one attribute.
Further, the items are linked to each other in the sequence by similarity relations in attributes of the items.
Suitably, the sequence generating system is implemented by generating a desired next item in the sequence on the basis of similarity relationships between the item and the sequence.
The desired-next-item is further generated by user profiling techniques and/or metadata analysis techniques.
The sequence may represent music titles.
The method according to the invention may further comprise the steps of providing the database with a parameter relating to a xe2x80x9ccontinuity/discontinuityxe2x80x9d mode on the sequence, a parameter relating to a xe2x80x9crepetitivityxe2x80x9d mode on the sequence, a parameter relating to a xe2x80x9clength of pastxe2x80x9d mode on the sequence, a parameter relating to a xe2x80x9cexplicit constraintsxe2x80x9d mode on said sequence and a parameter relating to the xe2x80x9cnumber of items to be generated at a timexe2x80x9d mode, respectively.
Likewise, the user profiling system may be implemented using a parameter relating to a xe2x80x9ccontinuity/discontinuityxe2x80x9d mode on a user profile.
In the above methods, the database may contain information representing a plurality of collections of descriptor/value pairs, each of the values for descriptors being selected from descriptor/value lists, and each of the descriptors is associated to a descriptor type.
Further, the descriptor types may at least comprise Integer-Type, Taxonomy-Type and Discrete-Type.
Further yet, at least some of the descriptor types may have mathematical similarity functions.
In the above methods of the invention, the database may comprise musical pieces, and the sequence of items may comprise music programs.
The database may contain data corresponding to musical pieces and the attribute(s) may express objective data associated with a item, such as a song title, author of the musical piece, duration of the musical piece, recording label . . .
Likewise, the database may contain data corresponding to musical pieces and the attribute(s) may express subjective data, associated with a item, which describe musical properties thereof, such as style, type of voice, music setup, type of instruments, tempo, type of melody, main theme of the lyrics . . .
There is also provided an implementation of the method mentioned above, for creating a user recommendation system, each recommendation taking into account both sequence coherence and user profile.
The invention also relates to an interactive radio station providing a personalised sequence of musical items, characterised in that the sequence is generated by the above methods, thereby taking into account user tastes interactively.
The invention further concerns a system adapted to implement the method of any one of claims 1 to 19, comprising a general-purpose computer and a monitor for display of the generated information. There is also provided a computer program product adapted to carry out any one of the above methods, when loaded into a general purpose computer.